/**
 * 有两个单链表中的元素均按照元素递增的次序，编写算法将两个单链表归并为一个按元素递减排序的单链表，
 * 并要求利用原来两个单链表的结点存放归并后的单链表
 */

#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

typedef struct LNode{
	struct LNode* next;
	int data;
} LNode, *LinkedList;

bool init(LinkedList &list);

bool insert(LinkedList &list, int data);

void print(LinkedList &list);

bool core(LinkedList &la, LinkedList &lb);

int main()
{
	LinkedList list1=NULL;
	LinkedList list2=NULL;
	init(list1);
	init(list2);
	insert(list2,1);
	insert(list2,2);
	insert(list2,2);
	insert(list2,2);
	insert(list1,3);
	insert(list1,5);
	insert(list2,5);
	insert(list2,8);
	insert(list2,9);
	insert(list2,12);	
	core(list1,list2);
	return 0;
}

bool init(LinkedList &list)
{
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->next=NULL;
	list=newNode;
	return true;
}

bool insert(LinkedList &list, int data)
{
	LinkedList node=list;
	while(node->next) node=node->next;
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->next=NULL;
	newNode->data=data;
	node->next=newNode;
	return true;
}

void print(LinkedList &list)
{
	LinkedList node=list->next;
	while(node)
	{
		printf("%d ",node->data);
		node=node->next;
	}
	printf("\n");
}

bool core(LinkedList &la, LinkedList &lb)
{
	LinkedList pa=la;	//链表la的遍历结点
	LinkedList pb=lb;	//链表lb的遍历结点
	
	LNode* node=NULL;	
	la->next=NULL;		//存放到la链表中
	
	while(pa && pb)
	{
		if(pa->data <= pb->data)
		{
			//结点pa中的元素小于等于pb中的元素
			node=pa->next;	//node存放较小结点的后继结点
			pa->next=la->next;
			la->next=pa;
			pa=node;		//回复la的遍历结点pa
		} else {
			//pa的元素大于pb的元素
			node=pb->next;
			pb->next=la->next;
			la->next=pb;
			pb=node;
		}
	}
	
	if(pa) pb=pa;
	
	//处理剩下的非空链表
	while(pb)
	{
		node=pb->next;		//依次插入到la中(头插法)
		pa->next=la->next;
		la->next=pb;
		pb=node;
	}
	free(lb);
	return true;
}